//https://leetcode.cn/problems/permutations/description/
//全排列
//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

int count;

void Creat(int* nums, int n, int pos, int* cur, bool* used, int** ret)
{
    if(pos == n)
    {
        memcpy(ret[count++], cur, sizeof(int) * n);
        return;
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            if(used[i] == false)
            {
                cur[pos] = nums[i];
                used[i] = true;
                Creat(nums, n, pos + 1, cur, used, ret);
                used[i] = false;
            }
        }
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 1;
    for(int i = 2; i <= numsSize; i++)
    {
        (*returnSize) *= i;
    }

    (*returnColumnSizes) = (int*)malloc(sizeof(int) * (*returnSize));
    for(int i = 0; i < (*returnSize); i++)
    {
        (*returnColumnSizes)[i] = numsSize;
    }

    int* cur = (int*)malloc(sizeof(int) * numsSize);
    bool* used = (bool*)calloc(numsSize, sizeof(bool));
    int** ret = (int**)malloc(sizeof(int*) * (*returnSize));
    for(int i = 0; i < (*returnSize); i++)
    {
        ret[i] = (int*)malloc(sizeof(int) * numsSize);
    }

    count = 0;

    //数组, 数组大小, 当前深度, 当前路径, 数组中已使用的数, 结果
    Creat(nums, numsSize, 0, cur, used, ret);
    return ret;
}